1. Field of the Invention
The present invention relates to allocating memory, and more particularly to making efficient use of resources for tracking different overlapping memory ranges.
2. Background Information
Client/server systems communicating over the Internet or other such communications means are well known in the art. Use of virtual memory is typical if not pervasive where an application (resident in the client) addresses a wide range of memory without regard to the actual memory hierarchies. Virtual memory is well understood in the art. Operating systems (OS) provide the appearance to multiple applications that they each have access to their own exclusive address space (Virtual Address space or VA). The OS maps the applications' accesses to the VA to a shared physical memory address space. Applications, in this discussion cannot directly access the physical memory, they can only do so via the OS. VA and physical memory are organized as equal sized pages, where each VA page maps to a single physical page. Hardware and software resources are allotted in proportion to the number of VA pages in order to timely perform the translation.
Since this mapping occurs whenever memory is accessed, in practice the actual mapping is performed in hardware in order to minimize the time overhead expense of mapping.
Use of VA provides several important benefits, including, inter alia: a) Security: since applications cannot directly access the pages in other applications; b) Run time resources: applications that have large VA space may have very small physical memory. In such a case, a “fault” occurs when the application accesses a VA page that has no corresponding physical page. The OS handles all such problems in a prescribed manner. The OS may allot physical memory or it may suspend or kill the application.
However, when the application can directly access the input/output (I/O) hardware that addresses physical memory without going through the OS, problems arise that are not handled by the OS. In such a case the I/O hardware operates outside the OS. The present invention is directed to such problems.
An application addresses VA while I/O hardware addresses physical memory. So the application VA address must be translated into a physical hardware address and the hardware must maintain a “shadow copy” of the virtual/physical mapping being managed by the OS to prevent chaos. The I/O maintains a translation table and must provide resources proportional to the number of VA pages associated with each application in order to support system operation. Minimizing the entries (and therefore the resources used) into such an I/O translation table is an objective of the present invention.
It is understood that the physical address may be addressed to memory that is remotely accessed via a communications network using a standard protocol, e.g. TCP/IP. Such protocols will not be further discussed as they is well known in the art.
The interface provided to an application for I/O to memory generally specifies a range of memory, e.g. a “read” system call generally will include a pointer into memory and a size or length. A library implementing this task does not usually know what ranges the application will specify in advance. Thus if the library accesses the hardware directly and wants to minimize the hardware resources required, it should check to ensure that ranges received from the application do not overlap with previous ranges, and if the ranges overlap, the library should re-use the hardware translating table entries previously inserted. If none of the previously inserted entries suffice, the OS must be invoked so that new entries can be made into the translation table. It will be more efficient in time and resources if existing entries are used.
System hardware and software resources are needed for storage of the translation tables, specifically, a shadow copy of the translation tables is needed and held in the IO hardware. As an application (or other applications running on the same processor) requires more blocks of memory, more IO hardware resources are required. If these memory allocations are separate and distinct without overlap there will be no problems. However, if the allocations overlap, and/or if there are many (say, thousands) allocations that may overlap, the use of many holding registers may be an inefficient use of IO hardware resources. It would be more efficient if the overlapping memory ranges were each coalesced into one range; this requires resources proportional to only the number of pages in the range, not to the number of overlapping ranges.
In applications that store and retrieve ranges of values, as discussed above, it would be necessary to discover all the stored ranges that overlap a key range when that key range is retrieved or stored. A linear search would include comparing the starting locations of any two ranges and the length or the ending locations to determine any overlap. For many range insertions, this will be very time and resource consuming. Hashing techniques might be considered appropriate for such a task. As is well known in the art, hash functions and tables have been very efficient for searching for or storing an item among a long list of such items. Briefly, an item is stored (or found) in a location by using the item as the argument in a function, called a hash function. The result is an address where the item is to be stored. When applied to memory systems, this hash address may indicate a group of locations, usually called a bucket, where a number of items can be stored or retrieved. The bucket contents are usually linearly examined.
Hashing has many variations, such as using pointers or storing pointers, and techniques to handle technical issues. For example, when there is no room in a bucket “a collision” occurs when the system tries to store another item in the bucket. One technique is to store the item in another location that is tracked in “a scatter diagram.” As is well known many such techniques have been developed with respect to “hashing.”
However, applying hashing to the problem of finding overlapping ranges is not effective. The difficulty is that hits in the range database (implying an overlap of a key range with a previously inserted range) must occur even when the key range has a different starting location, length and ending location from any other previously inserted range. It is evident that any hash function that guarantees to map any two overlapping ranges to the same value can only succeed by mapping all the ranges to the same value. Such a function, by definition, is inefficient.
In such systems as discussed herein, the conversion from virtual to physical memory addressing is accomplished while preserving data integrity, there must be a mechanism for controlling the physical memory and searching for memory ranges allocated that may overlap other previously allocated memory ranges. Again the searching is for page ranges allocated in the IO hardware. The present invention is directed toward this task.